package 动态规划.递归参数思考型;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/15 21:09
 */
public class lc6912新理解 {


    // 这个题 思想出现 问题了!


    /*
     我就偏偏 定义 状态
     f(index, state) 表示的 从 index ~ len 最长非递减 数组的长度, state ==0 表示 上一个 选择使 nums1, state = 1 表示上一个元素选择的使 nums2

     - 既然 当 index = 0 的时候, nums[index - 1] 需要特判, 那我 直接 从 index = 1 开始调用, 不就解决这个问题了嘛
     */

    public int recursion(int index, int state, int nums1[], int nums2[], Integer dp[][]) {
        if (index == nums1.length) {
            return 0;
        }
        if (dp[index][state] != null) {
            return dp[index][state];
        }
        //
        int ans = 0;
        if (state == 0) {// pre = nums1
            if (nums1[index - 1] <= nums2[index]) { // choose  nums2
                ans = recursion(index + 1, 1, nums1, nums2, dp) + 1;
            }
            if (nums1[index - 1] <= nums1[index]) { // choose nums1
                ans = Math.max(ans, recursion(index + 1, 0, nums1, nums2, dp) + 1);
            }
        } else {
            if (nums2[index - 1] <= nums2[index]) {
                ans = recursion(index + 1, 1, nums1, nums2, dp) + 1;
            }
            if (nums2[index - 1] <= nums1[index]) {
                ans = Math.max(recursion(index + 1, 0, nums1, nums2, dp) + 1, ans);
            }
        }
        return dp[index][state] = ans;
    }

    // 下面这样写是不对的!
    public int solve(int nums1[], int nums2[]) {
        Integer dp[][] = new Integer[nums1.length + 1][2];
        return Math.max(recursion(1, 0, nums1, nums2, dp), recursion(1, 1, nums1, nums2, dp)) + 1;
    }

    // 直接 改 dp 试一下
    // 我他妈吐了 啊, 这就是有问题, 这个题的状态定义, 不太适合  去 上一个的 state 来使用
    public int dp(int nums1[], int nums2[]) {
        int len = nums1.length, dp[][] = new int[len + 1][2];
        int ans = 0;
        for (int i = len - 1; i >= 1; i--) {
            if (nums1[i - 1] <= nums2[i]) {
                dp[i][0] = dp[i + 1][1] + 1;
            }
            if (nums1[i - 1] <= nums1[i]) {
                dp[i][0] = Math.max(dp[i + 1][0] + 1,dp[i][0]);
            }
            if (nums2[i - 1] <= nums2[i]) {
                dp[i][1] = dp[i + 1][1] + 1;
            }
            if (nums2[i - 1] <= nums2[i]) {
                dp[i][1] = Math.max(dp[i][1],dp[i + 1][0] + 1);
            }
            ans = Math.max(Math.max(dp[i][0],dp[i][1]),ans);
        }
        ans = Math.max(ans,Math.max(dp[1][0],dp[1][1]) + 1);
        return ans;
    }

    @Test
    public void test(){
        int nums1[] = {2,3,1};
        int nums2[] = {1,2,1};
        int dp = dp(nums1, nums2);
        System.out.println(dp);
    }

}
